Many navigation systems are based on satellite-based global positioning system (GPS) devices which have been applied in automobile navigation systems, see, e.g., U.S. Pat. Nos. 5,938,720, 5,928,307, 5,922,042, 5,912,635, 5,910,177, 5,904,728, 5,902,350, all incorporated herein by reference for all purposes. Such automobile navigation systems, however, are expensive and inconvenient to use. Many such systems are further not appropriate for walking. Therefore, there is a great need in the art to incorporate navigation systems in personal handheld devices.
However, there are several technical obstacles that prevent the incorporation of navigational capabilities in handheld devices for providing turn-by-turn real-time navigation services. One such obstacle is the amount of geographic data needed to provide reasonably detailed navigational information. Small handheld devices include cellular phones, personal digital assistants, or computers, however, the amount of embedded memory is limited and is impractical to store a large amount of geographic information. In existing automobile navigation systems, GPS systems are employed to provide information about the location and movement of a user. Geographic information is usually stored in a geographic mapping database stored on a CD-ROM, hard-disk drive device or other large capacity storage medium.
Another obstacle is that the lack of information processing power of small devices such as those mentioned above. For example, the information processing power of a cellular telephone is typically provided by an embedded microprocessor with limited memory. While the information processing power of embedded microprocessors is generally increasing, such processors are still not suitable for processor intensive real-time navigational tasks.
An additional obstacle is the insufficient location accuracy provided by current technology. Initial sources of inaccuracy of the GPS based systems, for example, are either imposed by the U.S. Department of Defense through Selective Availability (S/A), other sources of error are due to atmospheric and timing errors limiting the accuracy of a single GPS receiver to +/-50 meters. Methods exist which can be used to enchance accuracies to +/-5 meters. Such methods include Enhanced GPS systems (i.e., SnapTrack) and network based system (i.e., Truepoint). These methods use a known position, such as a survey control point, as a reference point to correct the GPS position error. These methods of correcting GPS positions are referred to as Differential GPS or DGPS. The DGPS corrections can be applied to the GPS data in real-time using data telemetry (radio modems). Toward expanding the use of DGPS, the United States and Candian Coast Guard are establishing a series of radio beacons to transmit the DGPS corrections for accurate navigation along the Great Lakes, the Mississippi River and tributaries, the Gulf Coast,and the Eastern and Western coasts of North America. However, such radio beacons are not available to consumers traveling in most inland locations.
Location information that is ambiguous due to a number of factors discussed above makes navigational systems difficult to develop. For example, if the user is driving in a downtown area with streets spaced close together, a GPS location within +/-50 meters is not adequate to give turn-by-turn directions. The GPS location information is thus considered ambiguous and inappropriate for navigation systems. In other situations, a GPS location within +/-50 meters is adequate for navigation purpose. For example, if a user is driving on a highway in a remote area without any nearby exits, the GPS location is sufficient for calculating further navigation directions. Thus, in such a situation, the GPS location is not ambiguous.
Current automobile GPS navigation systems make use of other sensors, such as accelerometers, speedometers, etc. plus some sophisticated filtering technology to improve the accuracy of a navigational system (see, e.g., U.S. Pat. No. 5,912,635, previously incorporated by reference for all purposes). In addition, many automobile-based navigational systems use map-aiding technology as well. However, for a navigational system implemented using handheld devices such as cellular telephones, it is impractical to have the handheld devices connected to external sensors, especially when the device is used while walking.
Accordingly, it would be desirable to provide a navigational system that provides accurate navigational instructions. It would further be desirable to provide a navigational system that can be implemented on an existing infrastructure and is adaptable to new infrastructures as they become available.
It would further be desirable to provide a navigational system that can be implemented on handheld devices with limited computational power as well as devices with enhanced computational power.
It would further be desirable to provide a navigational system that can make use of many forms of real time information to provide accurate location calculations as well as optimal navigation paths.